package br.ufrn.ciencomp.grafos;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Grafo {
	public enum Tipo {MATRIZ, LISTA}
	private Tipo tipo;
	private int[][] matrizAdj;
	private Vertice[] vertices;
	private LinkedList<Aresta> arestas;
	private int n;
	
	public Grafo(int n, Tipo tipo) {
		this.tipo = tipo;
		this.n = n;
		if(tipo == Tipo.LISTA) {
			vertices = new Vertice[n];
			arestas = new LinkedList<Aresta>();
		} else if(tipo == Tipo.MATRIZ) {
			matrizAdj = new int[n][n];
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					matrizAdj[i][j] = 0;
				}
			}
		}
	}
	
	public Tipo getTipo() {
		return tipo;
	}

	public int[][] getMatrizAdj() {
		return matrizAdj;
	}
	
	public Vertice getVertice(int i) {
		return vertices[i];
	}
	
	public Vertice[] getVertices() {
		return vertices;
	}
	
	public LinkedList<Aresta> getArestas() {
		return arestas;
	}
	
	public int getN() {
		return n;
	}
	
	public void addAresta(int origem, int destino, int peso) {
		if(tipo == Tipo.LISTA) {
			arestas.add(
					new Aresta(
							origem, 
							destino, 
							peso));
		} else if(tipo == Tipo.MATRIZ) {
			matrizAdj[origem][destino] = peso;
		}
	}
	
	public void addAresta(int origem, int destino) {
		if(tipo == Tipo.LISTA) {
			arestas.add(
					new Aresta(
							origem, 
							destino, 
							1));
		} else if(tipo == Tipo.MATRIZ) {
			matrizAdj[origem][destino] = 1;
		}
	}
	
	public boolean depthFirstSearch(int x, int y) {
		Stack<Integer> pilha = new Stack<Integer>();
		pilha.push(x);
		
		while(!pilha.isEmpty()) {
			x = pilha.pop();
			if(x == y)
				return true;
			vertices[x].setVisitado(true);
			for(Aresta a : arestas) {
				if(a.getOrigem() == x && !vertices[a.getDestino()].isVisitado() ||
						a.getDestino() == x && !vertices[a.getOrigem()].isVisitado())
					pilha.push(x);
			}
		}
		return false;
	}
	
	public boolean breadthFirstSearch(int x, int y) {
		Queue<Integer> fila = new LinkedList<Integer>();
		fila.add(x);
		
		while(!fila.isEmpty()) {
			x = fila.poll();
			if(x == y)
				return true;
			getVertice(x).setVisitado(true);
			for(Aresta a : arestas) {
				if(a.getOrigem() == x && !vertices[a.getDestino()].isVisitado() ||
						a.getDestino() == x && !vertices[a.getOrigem()].isVisitado())
					fila.add(x);
			}
		}
		return false;
	}
}